package com.tucc.hello.leetcode.no401_800.no477;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {4, 12, 6};
        System.out.println(solution.totalHammingDistance(nums));
    }

    public int totalHammingDistance(int[] nums) {
        int sum = 0;
        for (int i = 0; i < 30; i++) {
            int v1 = 0;
            for(int j = 0;j < nums.length;j ++){
                v1 += (nums[j] >> i) & 1;
            }
            int v0 = nums.length - v1;
            sum += v0 * v1;
        }
        return sum;
    }

    public int totalHammingDistanceBad(int[] nums){
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            for(int j = i + 1;j < nums.length;j ++){
                sum += totalHammingDistance(nums[i], nums[j]);
            }
        }
        return sum;
    }

    public int totalHammingDistance(int a, int b) {
        int c = a ^ b;
        int v = 0;
        while (c > 0) {
            if (c % 2 == 1) {
                v ++;
            }
            c = c >> 1;
        }
        return v;
    }

}
